package leetcode;

/*
204. 计数质数
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
*/

import java.util.Arrays;

public class problems_204 {

    public static void main(String[] args) {
        System.out.println(new Solution().countPrimes(1500000));
    }

    static class Solution {
        int countPrimes(int n) {
            boolean[] isPrim = new boolean[n];
            // 将数组都初始化为 true
            Arrays.fill(isPrim, true);
            for (int i = 2; i < n; i++)
                if (isPrim[i])
                    // i 的倍数不可能是素数了
                    for (int j = 2 * i; j < n; j += i)
                        isPrim[j] = false;

            int count = 0;
            for (int i = 2; i < n; i++)
                if (isPrim[i]) count++;

            return count;
        }
    }


//    static class Solution {
//        public int countPrimes(int n) {
//            if(n == 1) return 0;
//            if(n == 2) return 0;
//            if(n == 3) return 1;
//            if(n == 4) return 2;
//            int sum = 0;
//            for (int i = 2; i < n; i++) {
//                if(isprime(i)) sum++;
//            }
//            return sum;
//        }
//        // 质数判断
//        private boolean isprime(int num){
//            if(num == 2) return true;
//            if(num == 3) return true;
//            if(num % 2 == 0) return false;
//            for (int i = 3; i <= Math.sqrt(num); i++) {
//                if(num % i == 0) return false;
//            }
//            System.out.println(num);
//            return true;
//        }
//    }
}